package chapter03_binaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述：
 *      二叉树的序列化与反序列化
 * @author hl
 * @version 1.0
 * @date 2020/10/27 16:16
 */
public class Code_04_SerializeAndReconstructTree {
    private static StringBuilder res;

    public static String serialByPre(Node head){
        if (head == null) {
            return null;
        }
        res = new StringBuilder();
        serialByPreReCur(head);
        return res.toString();
    }
    public static void serialByPreReCur(Node head){
        if (head == null) {
            res.append("#!");
            return ;
        }
        res.append(head.val + "!");
        serialByPreReCur(head.left);
        serialByPreReCur(head.right);
    }
    public static Node reconstructTree(String tree){
        String[] split = tree.split("!");
        Queue<String> queue = new LinkedList<>();
        for (String value : split) {
            queue.offer(value);
        }
        return reconPre(queue);
    }

    private static Node reconPre(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")) {
            return null;
        }
        Node node = new Node(Integer.valueOf(value));
        node.left = reconPre(queue);
        node.right = reconPre(queue);
        return node;
    }

    public static String serialByLevel(Node head){
        if (head == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        StringBuilder res= new StringBuilder();
        res.append(head.val + "!");
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            if (poll.left != null) {
                res.append(poll.left.val + "!");
                queue.add(poll.left);
            }else{
                res.append("#!");
            }
            if (poll.right != null) {
                res.append(poll.right.val + "!");
                queue.add(poll.right);
            }else{
                res.append("#!");
            }
        }
        return res.toString();
    }
    public static Node reconByLevelString(String tree){
        String[] values = tree.split("!");
        int index = 0;
        Node head = generateNodeByString(values[index++]);
        Queue<Node> queue = new LinkedList<>();
        if (head != null) {
            queue.offer(head);
        }
        while(!queue.isEmpty()){
            Node node = queue.poll();
            node.left = generateNodeByString(values[index++]);
            node.right = generateNodeByString(values[index++]);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return head;
    }

    private static Node generateNodeByString(String value) {
        if (value.equals("#")) {
            return null;
        }
        return new Node(Integer.parseInt(value));
    }





}
